1. Field of the Invention
The invention relates generally to digital data processing systems, and more specifically to buffering systems for use in such data processing systems. More specifically, the invention provides a first in-first out buffer of adjustable size, or adjustable numbers of storage locations. This can facilitate the transfer of data between two elements through the buffer since, if the number of data words being transferred is less than the number of locations in the entire buffer, the number of locations in the buffer can be reduced so as to allow the first-loaded data word, after all of the data words have been fully loaded into the buffer, to be at the output end of the buffer and available to be transmitted to the receiving module. The invention thus ensures that time is not spent stepping the data words through the storage locations in the buffer after they have been loaded before the data is sent to the receiving module.
2. Description of the Prior Art
A digital data processing system generally includes three basic elements; namely, a memory element, an input/output element, and a processor element, all interconnected by one or more busses. The memory element stores data in addressable storage locations. This data includes both operands and instructions for processing the operands. The processor element causes data to be transferred or fetched, to it from the memory element, interprets the incoming data as either instructions or operands, and processes the operands in accordance with the instruction. The results are then stored in addressed locations in the memory element. An input/output element also communicates with the memory element in order to transfer data into the system and to obtain the processed data from it. The input/output elements normally operate in accordance with control information supplied to it by the processor element. The input/output elements may include, for example, printers, teletypewriters or keyboards and video display terminals, and may also include secondary data storage devices such as disk drives or tape drives.
It is common in data processing systems to use buffers to synchronize communications among the various elements forming the data processing system. These buffers can be "stacks", or last-in-first-out (LIFO) buffers, in which a receiving module retrieves data words in the reverse order in which they are loaded by a transmitting module. Alternatively, the buffers can be first-in-first-out (FIFO) storage elements in which a receiving module receives data words in the order in which they are loaded by a transmitting module. In some cases, buffers have the capacity for storing only single data words. In that case the LIFO and FIFO buffers are effectively the same. In other cases, the buffers may have several storage locations each of which can store a data word. The capacity of a buffer is selected by a designer based on a number of factors, including the speeds of the modules in transmitting and receiving data and the amount of data that is expected to be transferred between the two modules.
In a data transfer through a multiple-location FIFO buffer, data words are typically serially loaded into an input end, shifted through all of the storage locations in the buffer, and transmitted from an output end. If a transfer is of sufficient data words to use up all of the locations in the buffer, the data for the receiving module is at the output end of the buffer when all of the data have been loaded. However, if the transfer is not of sufficient data words to occupy all of the locations in the buffer, the receiving module will have to enable the buffer control to shift the data words through the buffer to the output end before it can begin receiving them.
A stack or LIFO buffer, on the other hand, does not have this problem. In a stack buffer, the output end and the input end are the same; data words do not have to be shifted through the buffer to reach the output end. However, two problems arise from the use of a stack buffer in some circumstances. First, the order of the data words received by a module from a stack buffer is reversed from the order in which they are loaded into the buffer. If the order is important to the receiving module, it will have to be designed with that buffering limitation in mind. Second, since the input and output ends are the same, only one module, the transmitting or receiving module, can use the stack buffer at a time, either to load or receive data. With a FIFO buffer, this limitation does not exist; the transmitting module can load data into the input end of a FIFO buffer at the same time that the receiving module is receiving data therefrom.